//统计一个数字在排序数组中出现的次数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2 
//
// 示例 2: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: 0 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// 
//
// 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-
//position-of-element-in-sorted-array/ 
//
// Related Topics 数组 二分查找 👍 407 👎 0


package leetcode.editor.cn;

// [剑指 Offer 53 - I]在排序数组中查找数字 I

public class ZaiPaiXuShuZuZhongChaZhaoShuZiLcof_JianZhiOffer53I {
    public static void main(String[] args) {
        Solution solution = new ZaiPaiXuShuZuZhongChaZhaoShuZiLcof_JianZhiOffer53I().new Solution();
        int ans = solution.search(new int[]{5, 7, 7, 8, 8, 10}, 8);
        System.out.println(ans);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            int l = -1, r = nums.length;
            int ml, mr;
            int m = l + ((r - l) >> 1);
            while (m != l && m != r) {
                if (nums[m] >= target) {
                    r = m;
                    m = l + ((m - l) >> 1);
                } else {
                    l = m;
                    m = m + ((r - m) >> 1);
                }
            }
            mr = r;
            l = -1;
            r = nums.length;
            m = l + ((r - l) >> 1);
            while (m != l && m != r) {
                if (nums[m] > target) {
                    r = m;
                    m = l + ((m - l) >> 1);
                } else {
                    l = m;
                    m = m + ((r - m) >> 1);
                }
            }
            ml = l;
            if (ml >= mr) {
                return ml - mr + 1;
            } else return 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}